//
// Created by 高森森 on 2022/2/13.
//

#ifndef LEETCODE_SOLUTION42_H
#define LEETCODE_SOLUTION42_H
#include<iostream>
#include<vector>
#include <numeric>

using namespace std;
class UnionFind3{
public:
    vector<int>father;//父亲节点
    vector<int>rank;//秩的数
    int n;//节点个数
public:
    //查询父结点
    UnionFind3(int _n):n(_n),rank(_n,1),father(_n){
        //iota函数，令father[i]=i;
        iota(father.begin(),father.end(),0);
    }
    int find(int x){
        if(x==father[x])
            return x;
        else{
            father[x]=find(father[x]);
            return father[x];
        }
    }
    //并查集合并
    bool merge(int i,int j){
        int x=find(i);
        int y=find(j);
        if(x==y){
            return false;
        }
        if(rank[x]<=rank[y]){
            father[x]=y;
        }
        else{
            father[y]=x;
        }
        if(rank[x]==rank[y]&&x!=y)
            rank[y]++;
        return true;
    }
    bool isConnected(int x,int y){
        x=find(x);
        y=find(y);
        return x==y;
    }
};

class Solution42 {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n=edges.size();
        vector<int>in(n+1,0);
        int target=-1;
        for(int i=0;i<n;i++){
            in[edges[i][1]]++;
            if(in[edges[i][1]]==2){
                target=edges[i][1];
                break;
            }
        }
        //说明没有入度为2的点，有可能成环，找到成环的点
        if(target==-1){
            UnionFind3 unionFind3(n+1);
            for(auto &e:edges){
                int x=unionFind3.find(e[0]);
                int y=unionFind3.find(e[1]);
                if(x!=y){
                    unionFind3.merge(x,y);
                }
                else{
                    return vector<int>{e[0],e[1]};
                }
            }
        }
        else{
            vector<vector<int>>two;
            UnionFind3 unionFind3(n+1);
            for(int i=0;i<n;i++){
                if(edges[i][1]==target){
                    two.push_back({edges[i][0],edges[i][1]});
                }else {
                    unionFind3.merge(edges[i][0],edges[i][1]);
                }
            }
            for(auto &edge:two){
                cout<<unionFind3.merge(edge[0],edge[1])<<endl;
                if(unionFind3.merge(edge[0],edge[1]))
                    return two[1];
                else
                    return two[0];
            }
        }
        return vector<int>{};
    }
};


#endif //LEETCODE_SOLUTION42_H
